﻿#include <iostream>

/**
 * 暴力递归
 * @param prev 前一个数是什么
 * @param remain 减去前一个数字还剩下多少
 */
static int divide(const int prev, const int remain)
{
	if (remain == 0)
	{
		// 找到了一种有效的方法
		return 1;
	}

	if (prev > remain)
	{
		// 前一个数字不能大于剩余的数字
		return 0;
	}

	int total = 0;
	for (int cur = prev; cur <= remain; cur++)
	{
		total += divide(cur, remain - cur);
	}

	return total;
}

static int divideByDp(int n)
{
	int size = n + 1;
	int* dp = (int*)malloc(size * size * sizeof(int));
	memset(dp, 0, size * size * sizeof(int));

	for (int prev = 0; prev <= n; prev++)
	{
		dp[prev] = 1;
	}

	for (int remain = 1; remain <= n; remain++)
	{
		for (int prev = remain; prev >= 0; prev--)
		{
			if (prev == remain)
			{
				dp[prev + remain * size] = dp[prev];
			}
			else
			{
				dp[prev + remain * size] = dp[prev + (remain - prev) * size] + dp[prev + 1 + remain * size];
			}
		}
	}

	int res = dp[1 + n * size];
	free(dp);
	return res;
}

/**
 * 给定一个正数1，裂开的方法有1种，(1)
 * 给定一个正数2，裂开的方法有2种，(1和1)、(2)
 * 给定一个正数3，裂开的方法有3种，(1、1、1)、(1、2)、(3)
 * 给定一个正数4，裂开的方法有5种，(1、1、1、1)、(1、1、2)、(1、3)、(2、2)、(4)
 * 给定一个正数n，求裂开的方法数。
 * 
 * 思路：
 * 动态规划优化状态依赖的技巧.
 * 通过观察举例，发现分裂的数字要按照从小到大排序，也就是说，一种方法内的数字，从左到右，前一个数字必须是≤后一个数字的。
 * 所以给定的n分裂，从1开始尝试，将每一种组合都列出。
 * 比如: 7
 * 分解为(1,6),(2,5),(3,4),(4,3),(5,2),(6,1),(7,0)
 * 其中(1,6)又可以分解为(1,5),(2,4),(3,3),(4,2),(5,1),(6,0)...
 * ...
 * 
 * 后一个数比前一个数小则直接按照无效处理。
 * 
 *             0   1   2   3   4   5   6   7   prev
 * -------------------------------------------------------
 *         0|  1   1   1   1   1   1   1   1
 *         1|  X   1   0   0   0   0   0   0
 *         2|  X   2   1   0   0   0   0   0
 *         3|  X   3   1   1   0   0   0   0
 *         4|  X   5   2   1   1   0   0   0
 *         5|  X   7   2   1   1   1   0   0
 *         6|  X  11   4   2   1   1   1   0
 *         7|  X  15   4   2   1   1   1   1
 *      remain
 * 
 * 由暴力递归得知，
 * prev==0时无效；remain==0时，填1; prev>remain时，填0. 
 依次填写表格如下：
 * dp(1,1)=dp(1,0)=1
 * dp(1,2)=dp(1,1)+dp(2,0)=2
 * dp(2,2)=dp(2,0)=1
 * dp(1,3)=dp(1,2)+dp(2,1)+dp(3,0)=3
 * dp(2,3)=dp(2,1)+dp(3,0)=1
 * dp(3,3)=dp(3,0)=1
 * dp(1,4)=dp(1,3)+dp(2,2)+dp(3,1)+dp(4,0)=5
 * dp(2,4)=dp(2,2)+dp(3,1)+dp(4,0)=2
 * dp(3,4)=dp(3,1)+dp(4,0)=1
 * dp(4,4)=dp(4,0)=1
 * dp(1,5)=dp(1,4)+dp(2,3)+dp(3,2)+dp(4,1)+dp(5,0)=7
 * dp(2,5)=dp(2,3)+dp(3,2)+dp(4,1)+dp(5,0)=2
 * dp(3,5)=dp(3,2)+dp(4,1)+dp(5,0)=1
 * dp(4,5)=dp(4,1)+dp(5,0)=1
 * dp(5,5)=dp(5,0)=1
 * dp(1,6)=dp(1,5)+dp(2,4)+dp(3,3)+dp(4,2)+dp(5,1)+dp(6,0)=11
 * dp(2,6)=dp(2,4)+dp(3,3)+dp(4,2)+dp(5,1)+dp(6,0)=4
 * dp(3,6)=dp(3,3)+dp(4,2)+dp(5,1)+dp(6,0)=2
 * dp(4,6)=dp(4,2)+dp(5,1)+dp(6,0)=1
 * dp(5,6)=dp(5,1)+dp(6,0)=1
 * dp(6,6)=dp(6,0)=1
 * dp(1,7)=dp(1,6)+dp(2,5)+dp(3,4)+dp(4,3)+dp(5,2)+dp(6,1)+dp(7,0)=15
 * dp(2,7)=dp(2,5)+dp(3,4)+dp(4,3)+dp(5,2)+dp(6,1)+dp(7,0)=4
 * dp(3,7)=dp(3,4)+dp(4,3)+dp(5,2)+dp(6,1)+dp(7,0)=2
 * dp(4,7)=dp(4,3)+dp(5,2)+dp(6,1)+dp(7,0)=1
 * dp(5,7)=dp(5,2)+dp(6,1)+dp(7,0)=1
 * dp(6,7)=dp(6,1)+dp(7,0)=1
 * dp(7,7)=dp(7,0)=1
 * 
 * 通过观察，得到的dp填写顺序应该按照remain从1到n，每一行prev从remain到0的顺序填写，这样写可以避免每个格子的for循环求和过程。
 */
int main_dividingPositiveNumber()
{
	int n = 8;
	int methodCount = divide(1, n);
	printf("%d\n", methodCount);
	methodCount = divideByDp(n);
	printf("%d", methodCount);
	return 0;
}